
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
    public final static int MK = (int)1e6;
    public final static List<Integer> prime = new ArrayList();
    public static final boolean[] is_prime = new boolean[MK+1];
    static{
        int k = 0;
        for(int i=2; i<=MK; i++){
            if(!is_prime[i]){
                prime.add(i);
                for(int j=i; j <= MK / i; j++)
                    is_prime[i*j] = true;
            }
        }
    }
    public List<List<Integer>> findPrimePairs(int n) {
        List<List<Integer>> ans = new ArrayList();
        if(n%2 > 0){
            if( n>4 && !is_prime[n-2]){
                List<Integer> tmp = new ArrayList();
                tmp.add(2);
                tmp.add(n-2);
                ans.add(tmp);
                return ans;
            }
            return ans;
        }
        for(int i = 0; i < prime.size(); i++){
            int x = prime.get(i);
            int y = n - x;
            if(x > y)break;
            if(!is_prime[y]){
                List<Integer> tmp = new ArrayList();
                tmp.add(x);
                tmp.add(y);
                ans.add(tmp);
            }
        }
        return ans;
    }
}
class Solution {
    public final static int MK = (int)1e6;
    public final static int[] prime = new int[100001];
    public static final boolean[] is_prime = new boolean[MK+1];
    static{
        int k = 0;
        for(int i=2; i<=MK; i++){
            if(!is_prime[i]){
                prime[k++] = i;
                for(int j=i; j <= MK / i; j++)
                    is_prime[i*j] = true;
            }
        }
    }
    public List<List<Integer>> findPrimePairs(int n) {
        List<List<Integer>> ans = new ArrayList();
        if(n%2 > 0){
            if( n>4 && !is_prime[n-2]){
                List<Integer> tmp = new ArrayList();
                tmp.add(2);
                tmp.add(n-2);
                ans.add(tmp);
                return ans;
            }
            return ans;
        }
        for(int i = 0; i < prime.length; i++){
            int x = prime[i];
            int y = n - x;
            if(x > y)break;
            if(!is_prime[y]){
                List<Integer> tmp = new ArrayList();
                tmp.add(x);
                tmp.add(y);
                ans.add(tmp);
            }
        }
        return ans;
    }
}
class Solution2 {
    public int longestAlternatingSubarray(int[] nums, int threshold) {
        int count = 0;
        for(int i=0; i < nums.length; i++){
            if(nums[i]%2 == 0 && nums[i] <= threshold){
                int max = 1;
                int flag = 0;
                for(int j=i+1; j<nums.length; j++){
                    if(flag == 0 && nums[j]%2 == 1 && nums[j] <= threshold){
                        max++;
                        flag = 1;
                        if(count < max)
                            count = max;
                    }else if(flag == 1 && nums[j]%2 == 0 && nums[j] <= threshold){
                        i = j-1;
                        max++;
                        flag = 0;
                        if(count < max)
                            count = max;
                    }else{
                        break;
                    }
                }
                count = count > max ? count : max;
            }
        }
        return count;
    }
}
class Solution1 {
    public int longestAlternatingSubarray(int[] nums, int threshold) {
        int count = 0;
        int i = 0;
        int ans = 0;
        while(i < nums.length){
            if(nums[i]>threshold || nums[i]%2 != 0){
                i++;
                continue;
            }
            int j = i;
            i++;
            while(i < nums.length && nums[i] <= threshold && nums[i]%2 != nums[i-1]%2){
                i++;
            }
            ans = ans > i - j ? ans : i - j;
        }
        return ans;
    }
}
public class Test {
    public static void main(String[] args) {
        boolean[] p = new boolean[3];
        List<Integer> a = new ArrayList();
        a.add(3);

        System.out.println(Arrays.toString(p));
    }
}
